#define _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 == 1) return false;
        stack<char> st;
        for (auto& e : s)
        {
            if (e == '(') st.push(')');
            else if (e == '[') st.push(']');
            else if (e == '{') st.push('}');
            else if (st.empty() || st.top() != e) return false;
            else st.pop();
        }
        return st.empty();
    }
};